# 二分查找模版

# 查找是否存在一个数：左闭右闭区间n=len(nums)-1，while用<=, mid找到直接返回，其他都要加减1因为mid已经被搜索过。
def binary_search_exist(nums, target):
    if len(nums) == 1:
        return True if nums[0] == target else False
    # 左闭右闭
    left, right = 0, len(nums) - 1
    # <=
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return True
        elif nums[mid] < target:
            # 继续搜索[left, mid + 1]
            left = mid + 1
        elif nums[mid] > target:
            # 继续搜索[left, mid - 1]
            right = mid - 1
    return False


# 查找目标数字左边界下标：左闭右开区间n=len(nums),while用<,mid查到right=mid，右边界找时不减1，因为【left，mid）和【mid+1，right）。
def binary_search_left(nums, target):
    if len(nums) == 1:
        return 0 if nums[0] <= target else 1
    # 注意区间，右开
    left, right = 0, len(nums)
    # <
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            # 不要退出，继续缩小上边界
            right = mid
        elif nums[mid] < target:
            # 继续搜索区间[mid + 1, right)
            left = mid + 1
        elif nums[mid] > target:
            # 继续搜索区间[left,mid)
            right = mid
    # 返回的是比target小的数字个数
    return left


# 查找目标数字左边界下标：左闭右开区间n=len(nums),while用<,mid查到left=mid，左边界找时不减1，因为【left，mid）和【mid+1，right）。
def binary_search_right(nums, target):
    if len(nums) == 1:
        return 1 if nums[0] >= target else 0
    # 左闭右开
    left, right = 0, len(nums)
    # <
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            left = mid + 1
        elif nums[mid] < target:
            #   继续搜索[mid + 1, right)
            left = mid + 1
        elif nums[mid] > target:
            #   继续搜索[left, mid)
            right = mid
        # 返回小于等于target的个数
    return right - 1


if __name__ == '__main__':
    print(binary_search_exist([1, 2, 2, 3, 4, 5, 5, 8, 9], 7))
    print(binary_search_left([1, 2, 2, 3, 4, 5, 5, 8, 9], 5))
    print(binary_search_right([1, 2, 2, 3, 4, 5, 5, 8, 9], 5))